package h0803;

import java.util.*;
/**
  * @description 最富裕的小家庭
  * @author 不知名帅哥
  * @date 2024/8/3 15:46
  * @version 1.0
*/
public class RichestSmallFamily2 {
    static List<List<Integer>> tree = new ArrayList<>();
    static int[] wealth;
    static int maxWealth = 0;

    public static void dfs(int node, int parent) {
        int currentWealth = wealth[node - 1]; // 当前节点财富值（节点从1开始编号，数组从0开始索引）
        
        // 遍历子节点
        for (int child : tree.get(node)) {
            if (child != parent) {
                dfs(child, node);
                currentWealth += wealth[child - 1];
            }
        }
        
        // 更新最富裕小家庭的财富和
        maxWealth = Math.max(maxWealth, currentWealth);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 成员总数
        wealth = new int[n];

        // 读入每个成员的财富值
        for (int i = 0; i < n; i++) {
            wealth[i] = scanner.nextInt();
        }

        // 初始化树的邻接表
        for (int i = 0; i <= n; i++) {
            tree.add(new ArrayList<>());
        }

        // 读入父子关系，构建树
        for (int i = 1; i < n; i++) {
            int parent = scanner.nextInt();
            int child = scanner.nextInt();
            tree.get(parent).add(child);
            tree.get(child).add(parent);
        }

        // 从节点1开始DFS遍历
        dfs(1, -1);

        // 输出最大财富和
        System.out.println(maxWealth);
    }
}
